package com;

import lombok.Data;

import java.util.Collection;
import java.util.Map;
import java.util.Set;

/**
 * 2-3 查找树
 */
public class TwoThreeSearchTree<Key extends Comparable<Key>, Val> implements Map<Key, Val> {

    private Node<Key, Val> root;

    private int size;

    @Data
    public static class Node<Key, Val> {

        Key leftKey;

        Val leftVal;

        Key rightKey;

        Val rightVal;

        Node<Key, Val> leftNode;

        Node<Key, Val> midNode;

        Node<Key, Val> rightNode;

        int N;

        public Node(Key rightKey, Val rightVal) {
            this.rightKey = rightKey;
            this.rightVal = rightVal;
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean containsKey(Object key) {
        return false;
    }

    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    @Override
    public Val get(Object key) {
        return null;
    }

    @Override
    public Val put(Key key, Val value) {

        if (this.root == null) {
            this.root = new Node<>(key, value);
            this.size++;
            return value;
        }


        return null;
    }


    protected Val put(Node<Key, Val> node, Key key, Val val) {

        int leftKeyCompareResult = 0;
        int rightKeyCompareResult = 0;
        boolean currentIsFull = currentNodeIsFull(node);
        if (node.leftKey != null) {

            leftKeyCompareResult = key.compareTo(node.leftKey);

            if (leftKeyCompareResult < 0) {
                if (currentIsFull) {
                    return this.put(node.leftNode, key, val);
                }
            } else if (leftKeyCompareResult == 0) {
//                左节点命中
                Val oldLeftValue = node.leftVal;
                node.leftVal = val;
                return oldLeftValue;
            } else if (node.rightNode == null) {

            }
        }
        if (node.rightKey != null) {
            rightKeyCompareResult = key.compareTo(node.rightKey);
            if (rightKeyCompareResult > 0) {
                if (node.rightNode == null) {
                    node.rightNode = new Node<>(key, val);
                    return null;
                } else {
                    return this.put(node.rightNode, key, val);
                }
            } else if (rightKeyCompareResult < 0) {
                if (leftKeyCompareResult > 0) {
                    if (node.midNode == null) {
                        node.midNode = new Node<>(key, val);
                        return null;
                    } else {
                        return this.put(node.midNode, key, val);
                    }
                }
            }
            Val oldRightVal = node.rightVal;
            node.rightVal = val;
            return oldRightVal;
        }
        return null;
    }

    private boolean currentNodeIsFull(Node<Key, Val> node) {
        return node.leftKey != null && node.rightKey != null;
    }

    @Override
    public Val remove(Object key) {
        return null;
    }

    @Override
    public void putAll(Map<? extends Key, ? extends Val> m) {

    }

    @Override
    public void clear() {

    }

    @Override
    public Set<Key> keySet() {
        return null;
    }

    @Override
    public Collection<Val> values() {
        return null;
    }

    @Override
    public Set<Entry<Key, Val>> entrySet() {
        return null;
    }


}
